package com.cat.chapter052;

/**
*   @description https://leetcode.cn/problems/largest-rectangle-in-histogram/
*   @author cat
*   @create 2025/7/24 09:26
*   @since JDK17
*/

public class Solution04 {
    static int N = ((int) (1e5 + 10));
    static int[][] ans = new int[N][2];
    static int[] stack = new int[N];
    public int largestRectangleArea(int[] heights) {
        int res = 0, n = heights.length, r = 0, cur;
        for (int i = 0; i < n; i++) {
            while (r > 0 && heights[stack[r - 1]] >= heights[i]) {
                cur = stack[--r];
                ans[cur][0] = r == 0 ? -1 : stack[r - 1];
                ans[cur][1] = i;
            }
            stack[r++] = i;
        }
        while (r > 0) {
            cur = stack[--r];
            ans[cur][0] = r == 0 ? -1 : stack[r - 1];
            ans[cur][1] = n;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ans[i][1] != -1 && heights[ans[i][1]] == heights[i]) {
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
        for (int i = 0; i < n; i++) {
            int left = ans[i][0], right = ans[i][1];
            if (left == -1 && right == n) right--;
            res = Math.max(res, heights[i] * (right - left));
        }
        return res;
    }
}
